/**
 * @file 099.最小路径之和.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-17
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution
{
public:
    int minPathSum(vector<vector<int>> &grid)
    {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(grid);
        for (int i = 1; i < m; ++i) {
            dp[i][0] += dp[i - 1][0];
        }
        for (int j = 1; j < n; ++j) {
            dp[0][j] += dp[0][j - 1];
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};

int main()
{
    vector<vector<int>> grid1 = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
    vector<vector<int>> grid2 = {{1, 2, 3}, {4, 5, 6}};
    cout << Solution().minPathSum(grid1) << endl;
    cout << Solution().minPathSum(grid2) << endl;
    return 0;
}